package leetcode_周赛._2023._08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 第 359 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/8/20 21:34
 */
public class _20 {

    /**
     * k-avoiding 数组的最小总和 <br />
     * 算法：数学
     *
     * @param n n 个正整数
     * @param k 任意两个数之和不等于 k
     */
    public int minimumSum(int n, int k) {
        int m = Math.min(n, k / 2);
        return (1 + m) * m / 2 + (k + k + n - m - 1) * (n - m) / 2;
    }

    /**
     * 销售利润最大化 <br />
     * 算法：动态规划 <br />
     * 枚举 end, 当前 i 的大小跟 i - 1 的大小有关
     *
     * @param n      n 间房子, 编号从 0 开始
     * @param offers 买房
     */
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        List<int[]>[] groups = new ArrayList[n];
        Arrays.setAll(groups, e -> new ArrayList<>());
        for (List<Integer> offer : offers) groups[offer.get(1)].add(new int[]{offer.get(0), offer.get(2)});
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            for (int[] offer : groups[i - 1]) dp[i] = Math.max(dp[i], dp[offer[0]] + offer[1]);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        new _20().longestEqualSubarray(Arrays.asList(1, 2, 1), 0);
    }

    /**
     * 找出最长等值子数组 <br />
     * 算法：滑动窗口(通过同向双指针实现) + 分组
     *
     * @param k 删除 k 个数
     */
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int ans = 0, n = nums.size();
        List<Integer>[] groups = new ArrayList[n];
        Arrays.setAll(groups, e -> new ArrayList<>());
        for (int i = 0; i < n; i++) groups[nums.get(i) - 1].add(i);
        for (List<Integer> group : groups) {
            // [left, right] 组成了一个滑动窗口, 这个滑动窗口中要删除的元素数量小于等于 k
            int left = 0;
            for (int right = 0; right < group.size(); right++) {
                while (group.get(right) - group.get(left) + 1 - (right - left + 1) > k)
                    ++left;
                ans = Math.max(ans, right - left + 1);
            }
        }
        return ans;
    }

}
